﻿
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using CatEars.Core.Collections;

namespace CatEars.Text
{
    /// <summary>
    /// 字符串对比
    /// </summary>
    public static class StringCompare
    {
        #region Levenshtein LevenshteinEx
        /// <summary>
        /// 计算编辑距离
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <returns>编辑距离</returns>
        public static int Levenshtein(string strA, string strB)
        {
            //有任意一个为空，则编辑距离为另一个的长度
            if (strA == null || strA.Length == 0)
            {
                if (strB == null) return 0;
                else return strB.Length;
            }
            if (strB == null || strA.Length == 0)
            {
                if (strA == null) return 0;
                else return strA.Length;
            }
            //按 长字符 短字符 存放
            string strL;
            string strS;
            if (strA.Length >= strB.Length)
            {
                strL = strA;
                strS = strB;
            }
            else
            {
                strL = strB;
                strS = strA;
            }
            int intLenL = strL.Length;
            int intLenS = strS.Length;

            //节省内存，直接使用2列，对比时交替使用
            int[][] intDiffMap = new int[2][];
            {
                int[] intDiffMap0 = new int[intLenS + 1];
                intDiffMap[0] = intDiffMap0;
                intDiffMap[1] = new int[intLenS + 1];
                for (int i = 0; i < intDiffMap0.Length; i++)
                {
                    intDiffMap0[i] = i;
                }
            }
            int[] intDiffMapCurrent = null;
            int[] intDiffMapPrevious;
            for (int intCharL = 0; intCharL < intLenL; intCharL++)
            {
                char chrL = strL[intCharL];

                intDiffMapCurrent = intDiffMap[(intCharL + 1) % 2];
                intDiffMapPrevious = intDiffMap[intCharL % 2];
                intDiffMapCurrent[0] = intCharL + 1;
                for (int intCharS = 0; intCharS < intLenS; intCharS++)
                {
                    char chrS = strS[intCharS];
                    int intMinValue = Math.Min(intDiffMapCurrent[intCharS],
                        Math.Min(intDiffMapPrevious[intCharS + 1], intDiffMapPrevious[intCharS]));
                    if (chrL != chrS)
                    {
                        intMinValue++;
                    }
                    intDiffMapCurrent[intCharS + 1] = intMinValue;
                }
            }
            return intDiffMapCurrent[intLenS];
        }
        /// <summary>
        /// 计算编辑距离(扩展为支持对比任意集合)
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <returns>编辑距离</returns>
        public static int LevenshteinEx<T>(T[] strA, T[] strB)
        {
            //有任意一个为空，则编辑距离为另一个的长度
            if (strA == null || strA.Length == 0)
            {
                if (strB == null) return 0;
                else return strB.Length;
            }
            if (strB == null || strA.Length == 0)
            {
                if (strA == null) return 0;
                else return strA.Length;
            }
            //按 长字符 短字符 存放
            T[] strL;
            T[] strS;
            if (strA.Length >= strB.Length)
            {
                strL = strA;
                strS = strB;
            }
            else
            {
                strL = strB;
                strS = strA;
            }
            int intLenL = strL.Length;
            int intLenS = strS.Length;

            //节省内存，直接使用2列，对比时交替使用
            int[][] intDiffMap = new int[2][];
            {
                int[] intDiffMap0 = new int[intLenS + 1];
                intDiffMap[0] = intDiffMap0;
                intDiffMap[1] = new int[intLenS + 1];
                for (int i = 0; i < intDiffMap0.Length; i++)
                {
                    intDiffMap0[i] = i;
                }
            }
            int[] intDiffMapCurrent = null;
            int[] intDiffMapPrevious;
            for (int intCharL = 0; intCharL < intLenL; intCharL++)
            {
                T chrL = strL[intCharL];

                intDiffMapCurrent = intDiffMap[(intCharL + 1) % 2];
                intDiffMapPrevious = intDiffMap[intCharL % 2];
                intDiffMapCurrent[0] = intCharL + 1;
                for (int intCharS = 0; intCharS < intLenS; intCharS++)
                {
                    T chrS = strS[intCharS];
                    int intMinValue = Math.Min(intDiffMapCurrent[intCharS],
                        Math.Min(intDiffMapPrevious[intCharS + 1], intDiffMapPrevious[intCharS]));
                    if (object.Equals(chrL, chrS))
                    {
                        intMinValue++;
                    }
                    intDiffMapCurrent[intCharS + 1] = intMinValue;
                }
            }
            return intDiffMapCurrent[intLenS];
        }
        #endregion

        #region LCSeq 最长公共子序列算法(不连续的) Longest common sub sequence
        /// <summary>
        /// 计算最长公共子序列长度
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <returns>最长公共子串长度</returns>
        public static int LCSeq_Len(string strA, string strB)
        {
            //有任意一个为空，则返回0
            if (string.IsNullOrEmpty(strA) || string.IsNullOrEmpty(strB))
            {
                return 0;
            }
            //完全相等，返回全部
            if (strA == strB)
            {
                return strA.Length;
            }
            //按 长字符 短字符 存放
            string strL;
            string strS;
            if (strA.Length >= strB.Length)
            {
                strL = strA;
                strS = strB;
            }
            else
            {
                strL = strB;
                strS = strA;
            }
            int intLenL = strL.Length;
            int intLenS = strS.Length;

            //节省内存，直接使用2列，对比时交替使用
            int[][] intDiffMap = new int[2][];
            {
                intDiffMap[0] = new int[intLenS + 1];
                intDiffMap[1] = new int[intLenS + 1];
            }
            int[] intDiffMapCurrent = null;
            int[] intDiffMapPrevious;
            for (int intCharL = 0; intCharL < intLenL; intCharL++)
            {
                char chrL = strL[intCharL];

                intDiffMapCurrent = intDiffMap[(intCharL + 1) % 2];
                intDiffMapPrevious = intDiffMap[intCharL % 2];
                for (int intCharS = 0; intCharS < intLenS; intCharS++)
                {
                    char chrS = strS[intCharS];
                    int intValue = intDiffMapPrevious[intCharS];
                    if (chrL == chrS)
                    {
                        intValue++;
                    }
                    int intMaxValue = Math.Max(intDiffMapCurrent[intCharS],
                        Math.Max(intDiffMapPrevious[intCharS + 1], intValue));
                    intDiffMapCurrent[intCharS + 1] = intMaxValue;
                }
            }
            return intDiffMapCurrent[intLenS];
        }

        /// <summary>
        /// 计算最长公共子序列基础计算算法
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <param name="intLen">最长公共子串长度</param>
        /// <returns>计算过程中间对象</returns>
        private static DictToList<int, LCSeqEntity> LCSeq_Base(
            string strA,
            string strB,
            out int intLen)
        {
            //按 长字符 短字符 存放
            string strL;
            string strS;
            bool pFlag = true;
            if (strA.Length >= strB.Length)
            {
                strL = strA;
                strS = strB;
            }
            else
            {
                pFlag = false;
                strL = strB;
                strS = strA;
            }
            int intLenL = strL.Length;
            int intLenS = strS.Length;

            //节省内存，直接使用2列，对比时交替使用
            int[][] intDiffMap = new int[2][];
            {
                intDiffMap[0] = new int[intLenS + 1];
                intDiffMap[1] = new int[intLenS + 1];
            }
            int[] intDiffMapCurrent = null;
            int[] intDiffMapPrevious;
            StringBuilder strResult = new StringBuilder(intLenS);
            DictToList<int, LCSeqEntity> collList = new DictToList<int, LCSeqEntity>();
            if (pFlag)
            {
                for (int intCharL = 0; intCharL < intLenL; intCharL++)
                {
                    char chrL = strL[intCharL];

                    intDiffMapCurrent = intDiffMap[(intCharL + 1) % 2];
                    intDiffMapPrevious = intDiffMap[intCharL % 2];
                    for (int intCharS = 0; intCharS < intLenS; intCharS++)
                    {
                        char chrS = strS[intCharS];
                        int intValue = intDiffMapPrevious[intCharS];
                        int intMaxValue;
                        if (chrL == chrS)
                        {
                            intValue++;
                            intMaxValue = Math.Max(intDiffMapCurrent[intCharS],
                                Math.Max(intDiffMapPrevious[intCharS + 1], intValue));
                            //var entity = new LCSeqEntity(intCharS, intCharL, intMaxValue - 1, chrS);
                            var entity = new LCSeqEntity(intCharL, intCharS, intMaxValue - 1, chrS);
                            collList.AddValue(entity.Value, entity);
                        }
                        else
                        {
                            intMaxValue = Math.Max(intDiffMapCurrent[intCharS],
                                Math.Max(intDiffMapPrevious[intCharS + 1], intValue));
                        }
                        intDiffMapCurrent[intCharS + 1] = intMaxValue;
                    }
                }
            }
            else
            {
                #region 从前面的分支拷贝 只有一行不一样
                for (int intCharL = 0; intCharL < intLenL; intCharL++)
                {
                    char chrL = strL[intCharL];

                    intDiffMapCurrent = intDiffMap[(intCharL + 1) % 2];
                    intDiffMapPrevious = intDiffMap[intCharL % 2];
                    for (int intCharS = 0; intCharS < intLenS; intCharS++)
                    {
                        char chrS = strS[intCharS];
                        int intValue = intDiffMapPrevious[intCharS];
                        int intMaxValue;
                        if (chrL == chrS)
                        {
                            intValue++;
                            intMaxValue = Math.Max(intDiffMapCurrent[intCharS],
                                Math.Max(intDiffMapPrevious[intCharS + 1], intValue));
                            var entity = new LCSeqEntity(intCharS, intCharL, intMaxValue - 1, chrS);
                            //var entity = new LCSeqEntity(intCharL, intCharS, intMaxValue - 1, chrS);
                            collList.AddValue(entity.Value, entity);
                        }
                        else
                        {
                            intMaxValue = Math.Max(intDiffMapCurrent[intCharS],
                                Math.Max(intDiffMapPrevious[intCharS + 1], intValue));
                        }
                        intDiffMapCurrent[intCharS + 1] = intMaxValue;
                    }
                }
                #endregion
            }
            intLen = intDiffMapCurrent[intLenS];
            return collList;
        }

        /// <summary>
        /// 计算最长公共子序列(冲突时排前面的优先)
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <returns>最长公共子串</returns>
        public static string LCSeq(string strA, string strB)
        {
            //有任意一个为空，则返回0
            if (string.IsNullOrEmpty(strA) || string.IsNullOrEmpty(strB))
            {
                return string.Empty;
            }
            //完全相等，返回全部
            if (strA == strB)
            {
                return strA;
            }
            //strA和strB正算反算结果不同，因为都是左对齐计算 反算变成右对齐
            int intLen;
            var collList = LCSeq_Base(strA, strB, out intLen);
            char[] chrResult = new char[intLen];
            if (FindLCSeq_BaseOne(chrResult, collList, int.MaxValue, int.MaxValue, intLen - 1))
            {
                return new string(chrResult);
            }
            else
            {
                //正常情况不会出现
                throw new NotSupportedException("程序逻辑错误");
            }
        }

        /// <summary>
        /// 计算所有公共子序列
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <returns>最长公共子串</returns>
        public static string[] LCSeq_All(string strA, string strB)
        {
            //有任意一个为空，则返回0
            if (string.IsNullOrEmpty(strA) || string.IsNullOrEmpty(strB))
            {
                return EmptyArray.StringArray;
            }
            //完全相等，返回全部
            if (strA == strB)
            {
                return new string[] { strA };
            }
            int intLen;
            //strA和strB正算反算结果不同，因为都是左对齐计算 反算变成右对齐
            var collList = LCSeq_Base(strA, strB, out intLen);
            char[] chrResult = new char[intLen];
            var result = FindLCSeq_BaseAll(chrResult, collList, int.MaxValue, int.MaxValue, intLen - 1).Distinct();
            return result.ToArray();
        }

        /// <summary>
        /// 递归求子串方法
        /// </summary>
        /// <param name="chrArr"></param>
        /// <param name="collList"></param>
        /// <param name="intLastAIndex"></param>
        /// <param name="intLastBIndex"></param>
        /// <param name="intLoc"></param>
        /// <returns>所有子串</returns>
        private static IEnumerable<string> FindLCSeq_BaseAll(
            char[] chrArr,
            DictToList<int, LCSeqEntity> collList,
            int intLastAIndex,
            int intLastBIndex,
            int intLoc)
        {
            //递归找所有串
            var coll = collList.GetList(intLoc);
            if (coll != null)
            {
                for (int i = 0; i < coll.Count; i++)
                {
                    var value0 = coll[i];
                    if (value0.AstrIndex >= intLastAIndex
                        || value0.BstrIndex >= intLastBIndex)
                    {
                        continue;
                    }
                    chrArr[intLoc] = value0.Chr;
                    if (intLoc == 0)
                    {
                        yield return new string(chrArr);
                    }
                    else
                    {
                        var results = FindLCSeq_BaseAll(chrArr, collList, value0.AstrIndex, value0.BstrIndex, intLoc - 1);
                        foreach (var result in results)
                        {
                            yield return result;
                        }
                    }
                }
            }
        }

        /// <summary>
        /// 递归求子串方法
        /// </summary>
        /// <param name="chrArr"></param>
        /// <param name="collList"></param>
        /// <param name="intLastAIndex"></param>
        /// <param name="intLastBIndex"></param>
        /// <param name="intLoc"></param>
        /// <returns>是否成功</returns>
        private static bool FindLCSeq_BaseOne(
            char[] chrArr,
            DictToList<int, LCSeqEntity> collList,
            int intLastAIndex,
            int intLastBIndex,
            int intLoc)
        {
            //递归找最长串
            var coll = collList.GetList(intLoc);
            if (coll != null)
            {
                for (int i = 0; i < coll.Count; i++)
                {
                    var value0 = coll[i];
                    if (value0.AstrIndex >= intLastAIndex
                        || value0.BstrIndex >= intLastBIndex)
                    {
                        continue;
                    }
                    chrArr[intLoc] = value0.Chr;
                    if (intLoc == 0
                        || FindLCSeq_BaseOne(chrArr, collList, value0.AstrIndex, value0.BstrIndex, intLoc - 1))
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        /// <summary>
        /// LCSeq 计算过程中间对象
        /// </summary>
        [DebuggerDisplay("{AstrIndex}  {BstrIndex}   {Value}   -> {Chr}")]
        private class LCSeqEntity
        {
            public LCSeqEntity(int intAstrIndex, int intBstrIndex, int intValue, char chrC)
            {
                AstrIndex = intAstrIndex;
                BstrIndex = intBstrIndex;
                Value = intValue;
                Chr = chrC;
            }

            public int AstrIndex { get; private set; }
            public int BstrIndex { get; private set; }
            public int Value { get; private set; }
            public char Chr { get; private set; }
        }
        #endregion

        #region StringDiff (LCSeq是计算公共子序列的，排除公共子序列剩下的就是2个字符串的差异部分)

        /// <summary>
        /// 计算2个字符串的差异 使用公共子序列进行排除（一般短文本不会有很多子串，找到的所有子序列全部标记相同）
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <returns>[0]来自strA [1]来自strB</returns>
        public static StringDiffResult StringDiff(string strA, string strB)
        {
            var result = new StringDiffResult();
            #region 前置判断
            //有任意一个为空
            if (string.IsNullOrEmpty(strA))
            {
                result.Result = -2;
                result.ValuesA = EmptyArray<StringDiffEntity>.Array;
                if (string.IsNullOrEmpty(strB))
                {
                    result.ValuesB = EmptyArray<StringDiffEntity>.Array;
                    return result;
                }
                else
                {
                    result.ValuesB = new StringDiffEntity[] { new StringDiffEntity(strB, false) };
                    return result;
                }
            }
            else if (string.IsNullOrEmpty(strB))
            {
                result.Result = -2;
                result.ValuesA = new StringDiffEntity[] { new StringDiffEntity(strA, false) };
                result.ValuesB = EmptyArray<StringDiffEntity>.Array;
                return result;
            }
            //完全相等，返回全部
            if (strA == strB)
            {
                result.Result = 1;
                result.ValuesA = new StringDiffEntity[] { new StringDiffEntity(strA, true) };
                result.ValuesB = new StringDiffEntity[] { new StringDiffEntity(strB, true) };
                return result;
            }
            #endregion
            int intLen;
            var collList = LCSeq_Base(strA, strB, out intLen);
            if (intLen == 0)
            {
                //没有相同的部分
                result.Result = -1;
                result.ValuesA = new StringDiffEntity[] { new StringDiffEntity(strA, false) };
                result.ValuesB = new StringDiffEntity[] { new StringDiffEntity(strB, false) };
                return result;
            }
            bool[] bufferA = new bool[strA.Length];
            int[] bufferTmpA = new int[intLen];
            bool[] bufferB = new bool[strB.Length];
            int[] bufferTmpB = new int[intLen];
            FindLCSeq_StringDiff(bufferA, bufferB, bufferTmpA, bufferTmpB,
                collList, int.MaxValue, int.MaxValue, intLen - 1);
            result.ValuesA = StringDiffResult.BuildResult(strA, bufferA).ToArray();
            result.ValuesB = StringDiffResult.BuildResult(strB, bufferB).ToArray();
            return result;
        }

        /// <summary>
        /// 递归求子串方法
        /// </summary>
        /// <param name="bufferA"></param>
        /// <param name="bufferB"></param>
        /// <param name="bufferTmpA"></param>
        /// <param name="bufferTmpB"></param>
        /// <param name="collList"></param>
        /// <param name="intLastAIndex"></param>
        /// <param name="intLastBIndex"></param>
        /// <param name="intLoc"></param>
        private static void FindLCSeq_StringDiff(
            bool[] bufferA,
            bool[] bufferB,
            int[] bufferTmpA,
            int[] bufferTmpB,
            DictToList<int, LCSeqEntity> collList,
            int intLastAIndex,
            int intLastBIndex,
            int intLoc)
        {
            //递归找所有串
            var coll = collList.GetList(intLoc);
            if (coll != null)
            {
                for (int i = 0; i < coll.Count; i++)
                {
                    var value0 = coll[i];
                    if (value0.AstrIndex >= intLastAIndex
                        || value0.BstrIndex >= intLastBIndex)
                    {
                        continue;
                    }
                    bufferTmpA[intLoc] = value0.AstrIndex;
                    bufferTmpB[intLoc] = value0.BstrIndex;
                    if (intLoc == 0)
                    {
                        //递归找所有子串，一般短文本不会有很多子串，找到的位置全部标记相同
                        foreach (var item in bufferTmpA)
                        {
                            bufferA[item] = true;
                        }
                        foreach (var item in bufferTmpB)
                        {
                            bufferB[item] = true;
                        }
                    }
                    else
                    {
                        FindLCSeq_StringDiff(bufferA, bufferB, bufferTmpA, bufferTmpB,
                            collList, value0.AstrIndex, value0.BstrIndex, intLoc - 1);
                    }
                }
            }
        }

        /// <summary>
        /// 字符串对比结果
        /// </summary>
#pragma warning disable 1591
        public class StringDiffResult
        {
            /// <summary>
            /// -2其中一个字符串无内容 -1完全不相同 0正常 1完全相同
            /// </summary>
            public int Result { get; set; }
            /// <summary>
            /// 第一个字符串的结果
            /// </summary>
            public StringDiffEntity[] ValuesA { get; set; }
            /// <summary>
            /// 第二个字符串的结果
            /// </summary>
            public StringDiffEntity[] ValuesB { get; set; }

            public IEnumerable<StringDiffEntity> GetValueA(bool blnCommon)
            {
                var coll = ValuesA;
                if (coll == null || coll.Length == 0) yield break;
                foreach (var item in coll)
                {
                    if (item.Common == blnCommon) yield return item;
                }
            }

            public IEnumerable<StringDiffEntity> GetValueB(bool blnCommon)
            {
                var coll = ValuesA;
                if (coll == null || coll.Length == 0) yield break;
                foreach (var item in coll)
                {
                    if (item.Common == blnCommon) yield return item;
                }
            }

            public static IEnumerable<StringDiffEntity> BuildResult(string strValue, bool[] buffer)
            {
                bool blnFlag = buffer[0];
                StringBuilder strBuffer = new StringBuilder();
                strBuffer.Append(strValue[0]);
                for (int i = 1; i < strValue.Length; i++)
                {
                    char chr = strValue[i];
                    bool blnFlag0 = buffer[i];
                    if (blnFlag != blnFlag0)
                    {
                        yield return new StringDiffEntity(strBuffer.ToString(), blnFlag);
                        strBuffer.Clear();
                        blnFlag = blnFlag0;
                    }
                    strBuffer.Append(chr);
                }
                if (strBuffer.Length > 0)
                {
                    yield return new StringDiffEntity(strBuffer.ToString(), blnFlag);
                }
            }
        }

        [DebuggerDisplay("{Value} {Common}")]
#pragma warning disable 1591
        public class StringDiffEntity
        {
            public StringDiffEntity(string strValue, bool blnCommon)
            {
                Value = strValue;
                Common = blnCommon;
            }

            public string Value { get; private set; }
            public bool Common { get; private set; }
        }

        #endregion

        #region LCStr 最长公共子字符串 Longest common sub string

        /// <summary>
        /// 计算最长公共子字符串
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <returns>最长公共子序列</returns>
        public static string LCStr(string strA, string strB)
        {
            //有任意一个为空，则返回0
            if (string.IsNullOrEmpty(strA) || string.IsNullOrEmpty(strB))
            {
                return "";
            }
            //完全相等，返回全部
            if (strA == strB)
            {
                return strA;
            }
            //按 长字符 短字符 存放
            string strL;
            string strS;
            if (strA.Length > strB.Length)
            {
                strL = strA;
                strS = strB;
            }
            else
            {
                strL = strB;
                strS = strA;
            }
            int intLenL = strL.Length;
            int intLenS = strS.Length;

            //节省内存，直接使用2列，对比时交替使用
            int[][] intDiffMap = new int[2][];
            {
                intDiffMap[0] = new int[intLenS + 1];
                intDiffMap[1] = new int[intLenS + 1];
            }
            int[] intDiffMapCurrent = null;
            int[] intDiffMapPrevious;
            int intMaxValue = 0;
            int intMaxValueIndex = -1;
            for (int intCharL = 0; intCharL < intLenL; intCharL++)
            {
                char chrL = strL[intCharL];

                intDiffMapCurrent = intDiffMap[(intCharL + 1) % 2];
                intDiffMapPrevious = intDiffMap[intCharL % 2];
                for (int intCharS = 0; intCharS < intLenS; intCharS++)
                {
                    char chrS = strS[intCharS];
                    int intValue = intDiffMapPrevious[intCharS];
                    if (chrL == chrS)
                    {
                        intValue++;
                        if (intMaxValue < intValue)
                        {
                            //记录长度
                            intMaxValue = intValue;
                            //记录结束位置
                            intMaxValueIndex = intCharS;
                        }
                    }
                    else
                    {
                        intValue = 0;
                    }
                    intDiffMapCurrent[intCharS + 1] = intValue;
                }
            }
            if (intMaxValue == 0) return "";
            else return strS.Substring(intMaxValueIndex - intMaxValue + 1, intMaxValue);
        }

        /// <summary>
        /// 计算所有公共子字符串
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <param name="intMinLen">子串最小长度</param>
        /// <returns>公共格式，按strA的相对位置存储</returns>
        private static Dictionary<int, int> LCStrs_Base(string strA, string strB, int intMinLen)
        {
            //按 长字符 短字符 存放
            string strL;
            string strS;
            bool pFlag = true;
            if (strA.Length >= strB.Length)
            {
                strL = strA;
                strS = strB;
            }
            else
            {
                pFlag = false;
                strL = strB;
                strS = strA;
            }
            int intLenL = strL.Length;
            int intLenS = strS.Length;

            //节省内存，直接使用2列，对比时交替使用
            int[][] intDiffMap = new int[2][];
            {
                intDiffMap[0] = new int[intLenS + 1];
                intDiffMap[1] = new int[intLenS + 1];
            }
            Dictionary<int, int> dictCache = new Dictionary<int,int>();
            int[] intDiffMapCurrent = null;
            int[] intDiffMapPrevious;
            if (pFlag)
            {
                for (int intCharL = 0; intCharL < intLenL; intCharL++)
                {
                    char chrL = strL[intCharL];

                    intDiffMapCurrent = intDiffMap[(intCharL + 1) % 2];
                    intDiffMapPrevious = intDiffMap[intCharL % 2];
                    for (int intCharS = 0; intCharS < intLenS; intCharS++)
                    {
                        char chrS = strS[intCharS];
                        int intValue = intDiffMapPrevious[intCharS];
                        if (chrL == chrS)
                        {
                            intValue++;
                            //限制intValue > 1一个字符不作为子串
                            if (intValue >= intMinLen)
                            {
                                //intKey为开始位置 intValue为字符串长度
                                //int intKey = intCharS - intValue + 1;
                                int intKey = intCharL - intValue + 1;
                                int intOldValue;
                                dictCache.TryGetValue(intKey, out intOldValue);
                                if (intValue > intOldValue)
                                {
                                    dictCache[intKey] = intValue;
                                }
                            }
                        }
                        else
                        {
                            intValue = 0;
                        }
                        intDiffMapCurrent[intCharS + 1] = intValue;
                    }
                }
            }
            else
            {
                #region 从前面的分支拷贝 只有一行不一样
                for (int intCharL = 0; intCharL < intLenL; intCharL++)
                {
                    char chrL = strL[intCharL];

                    intDiffMapCurrent = intDiffMap[(intCharL + 1) % 2];
                    intDiffMapPrevious = intDiffMap[intCharL % 2];
                    for (int intCharS = 0; intCharS < intLenS; intCharS++)
                    {
                        char chrS = strS[intCharS];
                        int intValue = intDiffMapPrevious[intCharS];
                        if (chrL == chrS)
                        {
                            intValue++;
                            //限制intValue > 1一个字符不作为子串
                            if (intValue >= intMinLen)
                            {
                                //intKey为开始位置 intValue为字符串长度
                                //int intKey = intCharL - intValue + 1;
                                int intKey = intCharS - intValue + 1;
                                int intOldValue;
                                dictCache.TryGetValue(intKey, out intOldValue);
                                if (intValue > intOldValue)
                                {
                                    dictCache[intKey] = intValue;
                                }
                            }
                        }
                        else
                        {
                            intValue = 0;
                        }
                        intDiffMapCurrent[intCharS + 1] = intValue;
                    }
                }
                #endregion
            }
            return dictCache;
        }

        /// <summary>
        /// 计算所有公共子字符串
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <param name="intMinLen">子串最小长度</param>
        /// <returns>所有公共子字符串</returns>
        public static string[] LCStrs(string strA, string strB, int intMinLen = 2)
        {
            //有任意一个为空，则返回0
            if (string.IsNullOrEmpty(strA) || string.IsNullOrEmpty(strB))
            {
                return EmptyArray.StringArray;
            }
            //完全相等，返回全部
            if (strA == strB)
            {
                return new string[] { strA };
            }
            var dictCache = LCStrs_Base(strA, strB, intMinLen);
            if (dictCache == null || dictCache.Count == 0)
            {
                return EmptyArray.StringArray;
            }
            else
            {
                List<string> result = new List<string>(dictCache.Count);
                for (int i = 0; i < strA.Length; ++i)
                {
                    int intLen;
                    if (!dictCache.TryGetValue(i, out intLen))
                    {
                        continue;
                    }
                    result.Add(strA.Substring(i, intLen));
                    //加上这行会排除一些子串，如  7890   789x90 正算反算 90有歧义
                    //不加上这行，2个字符串倒置得到的结果不一致，因为现在是以最左边的字符对齐（字典的key） 倒置变成以右边的对齐 会有一些歧义项
                    //i += intLen - 1;
                }
                return result.Distinct().ToArray();
            }
        }

        /// <summary>
        /// 计算所有公共子字符串
        /// </summary>
        /// <param name="strA">字符串1</param>
        /// <param name="strB">字符串2</param>
        /// <param name="intMinLen">子串最小长度</param>
        /// <returns>所有公共子字符串</returns>
        public static ICollection<KeyValuePair<int,string>> LCStrsWithIndex(
            string strA, string strB, int intMinLen = 2)
        {
            //有任意一个为空，则返回0
            if (string.IsNullOrEmpty(strA) || string.IsNullOrEmpty(strB))
            {
                return EmptyArray<KeyValuePair<int, string>>.Array;
            }
            //完全相等，返回全部
            if (strA == strB)
            {
                return new KeyValuePair<int, string>[] { new KeyValuePair<int, string>(0, strA) };
            }
            var dictCache = LCStrs_Base(strA, strB, intMinLen);
            if (dictCache == null || dictCache.Count == 0)
            {
                return EmptyArray<KeyValuePair<int, string>>.Array;
            }
            else
            {
                List<KeyValuePair<int, string>> result = new List<KeyValuePair<int, string>>(dictCache.Count);
                for (int i = 0; i < strA.Length; ++i)
                {
                    int intLen;
                    if (!dictCache.TryGetValue(i, out intLen))
                    {
                        continue;
                    }
                    var kv = new KeyValuePair<int, string>(i, strA.Substring(i, intLen));
                    result.Add(kv);
                    //加上这行会排除一些子串，如  7890   789x90 正算反算 90有歧义
                    //不加上这行，2个字符串倒置得到的结果不一致，因为现在是以最左边的字符对齐（字典的key） 倒置变成以右边的对齐 会有一些歧义项
                    //i += intLen - 1;
                }
                return result.ToArray();
            }
        }

        #endregion
    }
}
